/**********************************************************************
 * File:        DisjointSets_FJ
 * Description: An implementation of the Disjoint Sets data structure.
 *				The algorithms used are described in Introduction to Algorithms, 2/e
 * Author:		Fuad Jamour
 * Created:		Fri Sep 18 15:21:46 GMT 2009
 **********************************************************************/

#ifndef	DISJOINTSETS
#define DISJOINTSETS
#include <map>
#include <list>
using namespace std;

template <class T>
class DisjointSets {
	struct node {
		T		v;
		node*	repNodePtr;//pointer to the representative of a set
		node*	nextNodePtr;
		node*	tailNodePtr;
	};

	map<T, node*>	setsMap;//map of pointers to all of the elements in the sets,
							//used to find a value's representative quickly

	//Returns a pointer to v's representative, used internally
	node* internalFindSet(T v) {
		if(setsMap[v] != NULL)
			return (setsMap[v]->repNodePtr);
	}

public:
	~DisjointSets() {
		for(map<T, node*>::iterator it = setsMap.begin(); it != setsMap.end(); it++) {
			delete it->second;
		}
		setsMap.clear();
	}
	//Makes a new set with single element with the value v
	void makeSet(T v) {
		node*	nodePtr = new node;
		nodePtr->nextNodePtr = NULL;
		nodePtr->repNodePtr = nodePtr;
		nodePtr->tailNodePtr = nodePtr;
		nodePtr->v = v;
		setsMap[v] = nodePtr;		
	}

	//Returns the value of the representative of v
	int	findSet(T v) {
		return (internalFindSet(v)->v);
	}

	//Merges the set x and the set y
	inline void unionSet(T x, T y) {
		node* rep1 = internalFindSet(x);
		node* rep2 = internalFindSet(y);
		if(rep1 == rep2) return;//the elements belongs to the same set, nothing to do
		//node* list1Tail = rep1->tailNodePtr;
		node* it;
		for(it = rep2; it != NULL; it = it->nextNodePtr) {
			it->repNodePtr = rep1;
		}

		rep1->tailNodePtr->nextNodePtr = rep2;
		rep1->tailNodePtr = rep2->tailNodePtr;
		//for(it = rep1; it != NULL; it = it->nextNodePtr) {
		//	it->tailNodePtr = rep2->tailNodePtr;
		//}
		//list1Tail->nextNodePtr = rep2;
	}

	//List of the representatives
	void representativesList(list<T>* repsList) {
		repsList->clear();
		list<T>::iterator list_it;
		std::map<T, node*>::iterator setsMap_it;
		

		for(setsMap_it = setsMap.begin(), list_it = repsList->begin();
			setsMap_it != setsMap.end(); setsMap_it++) {
				repsList->insert(list_it, setsMap_it->second->repNodePtr->v);
		}
	}
};


#endif